import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-01
 * Time: 15:54
 */
public class UnionFindSet {
    public int[] elem;
    public UnionFindSet(int size){
        this.elem=new int[size];
//        初始值全部为　-1, 表示每个节点都是 单独的
        Arrays.fill(this.elem, -1);
    }


    public void union(int index1, int index2){
        if(index1<0||index2<0){
            throw new IndexOutOfBoundsException("数字范围不合法, 是负数");
        }
        int root1=findRoot(index1);
        int root2=findRoot(index2);
        if(root1==root2){
//            本身就是同一个集合的
            return ;
        }
//        第一棵树的子节点数目变成两棵树的节点数目之和
        elem[root1]=elem[root1]+elem[root2];
//        第二个节点的父亲节点就是第一个节点
        elem[root2]=root1;
    }

    /**
     *  判断两个节点是否在同一颗树上
     *  即两个节点是否有关系
     * @return
     */
    public boolean isSameUnionFindSet(int index1, int index2){
        if(index1<0||index2<0){
            throw new IndexOutOfBoundsException("数字范围不合法, 是负数");
        }
        int root1=findRoot(index1);
        int root2=findRoot(index2);
        if(root1==root2){
            return true;
        }
        return false;
    }

    /**
     * 找一个节点的根节点
     * @param index 下标(或者说就是 值 )
     * @return
     */
    public int findRoot(int index){
        if(index<0){
            throw new IndexOutOfBoundsException("数字范围不合法, 是负数");
        }
//        一直往上找, 最后下标值为负数的就是根
        while(elem[index]>=0){
            index=elem[index];
        }
        return index;
    }

    /**
     *  得到不同集合的数量
     * @return
     */
    public int getCount(){
        int count=0;
        for (int x:elem) {
            if(x<0){
                count++;
            }
        }
        return count;
    }

    public void print(){
        for (int x:elem) {
            System.out.print(x+ " ");
        }
        System.out.println();
    }

}
